/*
 * @(#)XfdmActiveRules.java        1.0 2000/05/09
 *
 * This file is part of Xfuzzy 3.0, a design environment for fuzzy logic
 * based systems.
 *
 * (c) 2000 IMSE-CNM. The authors may be contacted by the email address:
 *                    xfuzzy-team@imse.cnm.es
 *
 * Xfuzzy is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by
 * the Free Software Foundation.
 *
 * Xfuzzy is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * for more details.
 */

package xfuzzy.xfdm.model.algorithm;

import xfuzzy.lang.*;
import xfuzzy.xfdm.model.XfdmAlgorithm;
import xfuzzy.xfdm.model.XfdmConfig;
import xfuzzy.xfds.XfdsDataSet;

/**
 * Clase que desarrolla el algoritmo Fuzzy-ID3
 * 
 * @author Francisco Jos� Moreno Velo
 *
 */
public class XfdmFuzzyID3 extends XfdmAlgorithm {

	//----------------------------------------------------------------------------//
	//                            MIEMBROS PRIVADOS                               //
	//----------------------------------------------------------------------------//

	/**
	 * Umbral de certeza de los patrones de datos
	 */
	private double threshold;
	
	//----------------------------------------------------------------------------//
	//                                CONSTRUCTOR                                 //
	//----------------------------------------------------------------------------//

	/**
	 * Constructor
	 */
	public XfdmFuzzyID3(double t){
		this.threshold = t;
	}

	/**
	 * Constructor
	 */
	public XfdmFuzzyID3(){
		this.threshold = 0.5;
	}

	//----------------------------------------------------------------------------//
	//                             M�TODOS P�BLICOS                               //
	//----------------------------------------------------------------------------//

	/**
	 * Indica si el algoritmo necesita que las variables de entrada tengan creadas
	 * las funciones de pertenencia. En caso contrario el algoritmo debe encargarse
	 * de dar contenido a los tipos de las variables de entrada.
	 */
	public boolean needInputMemFuncs() {
		return true;
	}
	
	/**
	 * Indica si el algoritmo necesita que las variables de salida tengan creadas
	 * las funciones de pertenencia. En caso contrario el algoritmo debe encargarse
	 * de dar contenido a los tipos de las variables de salida.
	 */
	public boolean needOutputMemFuncs() {
		return true;
	}

	/**
	 * Indica si el algoritmo necesita que la estructura del sistema est� creada.
	 * Este requisito es propio de los algoritmo que contienen alguna etapa de
	 * optimizaci�n param�trica.
	 * @return
	 */
	public boolean needSystemStructure() {
		return false;
	}

	/**
	 * Indica si el algoritmo es v�lido para problemas de clasificaci�n
	 * @return
	 */
	public boolean supportsClassification() {
		return true;
	}
	
	/**
	 * Indica si el algoritmo es v�lido para problemas de regresi�n
	 * @return
	 */
	public boolean supportsRegression() {
		return false;
	}

	/**
	 * Obtiene el nombre del algoritmo
	 */
	public String toString() {
		return "FuzzyID3";
	}

	/**
	 * Representaci�n en el fichero de configuraci�n
	 */
	public String toXML() {
		String eol = System.getProperty("line.separator", "\n");
		String code = "\t\t<algorithm name=\"FuzzyID3\" >"+eol;
		code += "\t\t\t<param name=\"threshold\" value=\""+threshold+"\" ></param>"+eol;
		code +=	"\t\t</algorithm>";
		return code;
	}

	/**
	 * Obtiene el tipo de base de conocimiento que genera el algoritmo
	 */
	public int getKnowledgeBaseKind() {
		return KnowledgeBase.RULE_SET;
	}

	/**
	 * Obtiene un duplicado del objeto
	 */
	public Object clone() {
		return new XfdmFuzzyID3(threshold);
	}

	/**
	 * Asigna el valor del umbral de pertenencia de los patrones
	 * @param t
	 */
	public void setThreshold(double t) {
		this.threshold = t;
	}
	
	/**
	 * Obtiene el valor del umbral de pertenencia de los patrones
	 * @return
	 */
	public double getThreshold() {
		return this.threshold;
	}
	
	/**
	 * Genera el contenido de la base de conocimiento a partir de los datos
	 */
	public void extractKnowlegde(KnowledgeBase base, XfdmConfig config) {
		XfdsDataSet dataset = config.getDataSet();
		Variable[] ivar = base.getInputs();
		Variable[] ovar = base.getOutputs();
		Type[] itype = new Type[ivar.length];
		for(int i=0; i<ivar.length;i++) itype[i] = ivar[i].getType();
		
		XfdmFuzzyDataSet fzdataset = new XfdmFuzzyDataSet(dataset,itype,ovar[0].getType());
		XfdmDecisionTreeNode tree = computeFuzzyID3(fzdataset,base);		
		fillRulebase(base, null, tree);
	}
	
	
	//----------------------------------------------------------------------------//
	//                             M�TODOS PRIVADOS                               //
	//----------------------------------------------------------------------------//

	/**
	 * Desarrolla el algoritmo FuzzyID3
	 */
	private XfdmDecisionTreeNode computeFuzzyID3(XfdmFuzzyDataSet dataset, KnowledgeBase base) {
		int num_patterns = dataset.certainty.length;
		Variable[] ovar = base.getOutputs();
		Type otype = ovar[0].getType();
		
		// Primer caso base: que no queden patrones
		// if(num_patterns ==  0) return new XfdmDecisionTreeNode(otype,0);
		if(num_patterns ==  0) return null;
		
		// Segundo caso base: que todos los patrones sean de la misma clase
		LinguisticLabel[] classifMF = otype.getAllMembershipFunctions();
		int classes = 0;
		int classifIndex = 0;
		for(int i=0; i<classifMF.length; i++) {
			for(int p=0; p<num_patterns; p++) if(dataset.output[p][i] > 0) { classes++; classifIndex = i; break; }
		}
		if(classes <= 1) return new XfdmDecisionTreeNode(otype, classifIndex);

		// Tercer caso base: que no queden atributos de entrada
		if(dataset.getAttrib().length == 0) {
			double max = -1;
			classifIndex = -1;
			for(int i=0; i<classifMF.length; i++) {
				double mu = 0;
				for(int p=0; p<num_patterns; p++) mu += dataset.output[p][i];
				if(mu>max) { max = mu; classifIndex = i; }
			}
			return new XfdmDecisionTreeNode(otype, classifIndex);
		}
		
		// Caso general
		Type[] attrib = dataset.getAttrib();
		double minEntropy = Double.MAX_VALUE;
		int bestAttrib = -1;
		for(int i=0; i<attrib.length; i++) {
			double entropy = computeEntropy(dataset,i,base);
			if(entropy < minEntropy) { minEntropy = entropy; bestAttrib = i; }
		}
		
		Type best = attrib[bestAttrib];
		LinguisticLabel[] mf = best.getAllMembershipFunctions();
		XfdmDecisionTreeNode[] branch = new XfdmDecisionTreeNode[mf.length];
		Operatorset opset = base.getOperatorset();
		for(int i=0; i<mf.length; i++) {
			XfdmFuzzyDataSet datasubset = new XfdmFuzzyDataSet(dataset,bestAttrib);
			double[] cert = new double[num_patterns];
			for(int p=0; p<num_patterns; p++) {
				cert[p] = opset.and.compute(dataset.certainty[p],dataset.input[p][bestAttrib][i]);
			}
			datasubset.certainty = cert;
			datasubset.prune(threshold);
			branch[i] = computeFuzzyID3(datasubset,base);
		}
		return new XfdmDecisionTreeNode(best,branch);
	}
	
	/**
	 * Calcula la entrop�a de informaci�n del atributo "attr" en el conjunto de datos
	 * @param dataset
	 * @param attr
	 * @return
	 */
	private double computeEntropy(XfdmFuzzyDataSet dataset, int attr, KnowledgeBase base) {
		Operatorset opset = base.getOperatorset();
		Binary and = opset.and;
		Binary imp = opset.imp;
		double entropy = 0;
		double totalmu = 0;
		Type attrib = dataset.getAttrib()[attr];
		LinguisticLabel[] mf = attrib.getAllMembershipFunctions();
		int num_classes = dataset.getClassif().getAllMembershipFunctions().length;
		int num_patterns = dataset.certainty.length;
		
		for(int i=0; i<mf.length; i++) {
			double mfentropy = 0;
			double mu = 0;
			double[] pc = new double[num_classes];
			for(int p=0; p<num_patterns; p++) {
				double mup = and.compute(dataset.certainty[p], dataset.input[p][attr][i]);
				mu += mup;
				for(int c=0; c<num_classes; c++) {
					pc[c] += imp.compute(mup,dataset.output[p][c]); 
				}
			}
			for(int c=0; c<num_classes; c++) {
				if(mu>0 && pc[c]>0) mfentropy -= ( pc[c]/mu ) * Math.log(pc[c]/mu); 
			}
			
			totalmu += mu;
			entropy += mu*mfentropy;
		}
		
		return entropy/totalmu;
	}
	
	/**
	 * Expande el �rbol de decisi�n a�adiendo las reglas a la base de reglas
	 * @param base
	 * @param rel
	 * @param tree
	 */
	private void fillRulebase(KnowledgeBase base, Relation rel, XfdmDecisionTreeNode tree) {
		if(tree == null) {
			return;
		} else if(tree.getKind() == XfdmDecisionTreeNode.LEAF) {
			Variable output = base.getOutputs()[0];
			Type type = output.getType();
			LinguisticLabel[] mf = type.getAllMembershipFunctions();
			Conclusion conc = new Conclusion(output,mf[tree.getClassifMF()],base);
			Rule rule = new Rule(rel);
			rule.add(conc);
			((RuleSet) base).addRule(rule);
		} else {
			Variable[] inputs = base.getInputs();
			Type type = tree.getAttrib();
			LinguisticLabel[] mf = type.getAllMembershipFunctions();
			Variable input = null;
			for(int i=0; i<inputs.length; i++) if(inputs[i].getType() == type) input = inputs[i];
			
			XfdmDecisionTreeNode[] branch = tree.getBranches();
			for(int i=0; i<branch.length; i++) {
				Relation sel = new SingleRelation(Relation.IS,input,mf[i],base);
				if(rel != null) sel = new BinaryRelation(Relation.AND,rel,sel,base);
				fillRulebase(base,sel,branch[i]);
			}
		}
	}

}


